package com.copa.l720;

import java.util.HashMap;

/**
 * @author copa
 * @createDate 2022-07-03 20:51
 * @function 字典树法
 */

/**
 * 字典树
 */
class Trie {
    // 子节点
    public HashMap<Character, Trie> children = new HashMap<>();
    // 是否存在数组的值
    public boolean isEnd;
}

public class Test2 {

    public String longestWord(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        // 创建字典树
        Trie root = new Trie();
        for (String word : words) {
            Trie cur = root;
            for (char c : word.toCharArray()) {
                if (cur.children.containsKey(c)) {
                    // 如果该节点存在该值，继续遍历
                    cur = cur.children.get(c);
                } else {
                    // 如果该节点不存在该值，则需要先创建，然后再遍历
                    Trie newNode = new Trie();
                    cur.children.put(c, newNode);
                    cur = newNode;
                }
            }
            // 每一个数组的word创建好后，设置为true，代表该节点有这个数组里面的word
            cur.isEnd = true;
        }

        // 开始正题
        String result = "";
        for (String word : words) {
            Trie cur = root;
            if (word.length() > result.length()
                    || (word.length() == result.length() && word.compareTo(result) < 0)) {
                // 如果符合上述条件，则遍历该word的每一个字符是否符合题意
                // 这个代表该word是否符合要求
                boolean isWord = true;
                for (char c : word.toCharArray()) {
                    cur = cur.children.get(c);
                    if (!cur.isEnd) {
                        // 没有逐步添加一个字母，不符合题意，直接退出
                        isWord = false;
                        break;
                    }
                }
                result = isWord ? word : result;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[] words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
        //String[] words = {"yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"};
        System.out.println(new Test2().longestWord(words));
    }
}
